package com.sheng.leetcode.year2022.month08.day25;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/08/25
 *
 * 5. 最长回文子串
 *
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 *
 * 示例 2：
 * 输入：s = "cbbd"
 * 输出："bb"
 *
 * 提示：
 *
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母组成
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0005 {

    @Test
    public void test01() {
        String s = "babad";
//        String s = "cbbd";
//        String s = "a";
        System.out.println(new Solution5().longestPalindrome(s));
    }
}
class Solution5 {
//    public String longestPalindrome(String s) {
//        // 超时
//        int length = s.length();
//        int max = 0;
//        String str = "";
//        for (int i = 0; i < length; i++) {
//            for (int j = i + 1; j < length + 1; j++) {
//                String substring = s.substring(i, j);
//                if (judge(substring) && substring.length() > max) {
//                    max = substring.length();
//                    str = substring;
//                }
//            }
//        }
//        return str;
//    }
//
//    public boolean judge(String str) {
//        for (int i = 0; i < str.length() / 2; i++) {
//            if (str.charAt(i) != str.charAt(str.length() - i - 1)) {
//                return false;
//            }
//        }
//        return true;
//    }

    public String longestPalindrome(String s) {
        // 动态规划
        // 字符串长度
        int length = s.length();
        // 如果字符串长度小余2，则直接返回（单个字符一定是回文字符串）
        if (length < 2) {
            return s;
        }
        // 最大长度
        int max = 1;
        // 最长回文子串的起始坐标，用于取出字符串
        int begin = 0;
        // 存储是否是回文串
        boolean[][] dp = new boolean[length][length];
        char[] chars = s.toCharArray();
        // 单个字符一定是回文
        for (int i = 0; i < length; i++) {
            dp[i][i] = true;
        }

        for (int j = 1; j < length; j++) {
            for (int i = 0; i < j; i++) {
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;
                } else {
                    // 长度为2或3是，肯定是回文。即除去chars[i]和 chars[j]后，只要1个或0个字符。防止出现例如 i=2 j=3情况下 查看dp[3][2]。
                    if (j - i < 2) {
                        dp[i][j] = true;
                    } else {
                        // 排除头尾元素后，是否是回文串
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 如果这一段是回文，并且这段字符串的长度大于之前的最大长度
                if (dp[i][j] && j - i + 1 > max) {
                    max = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, max + begin);
    }
}
